﻿using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_31 : BaseProblem
    {
        public override object GetResult()
        {
            var val = new[] {1, 2, 5, 10, 20, 50, 100, 200};

            return GetDiffCount(val, 200).Count;
        }

        public static List<int[]> GetDiffCount(int[] vals, int max)
        {
            var curr = new int[vals.Length];
            var res = new List<int[]>();
            GetDiffCountsRec(ref vals, ref res, curr, 0, max);
            return res;
        }

        private static void GetDiffCountsRec(ref int[] val, ref List<int[]> res, int[] current, int index, int max)
        {
            if (index >= val.Length) return;
            var kf = 0;
            while (true)
            {
                var q = val[index]*kf;
                if (q < max)
                {
                    current[index] = kf;
                    GetDiffCountsRec(ref val, ref res, current, index+1,max - q);
                }
                if (q == max)
                {
                    current[index] = kf;
                    res.Add(current);
                    return;
                }
                if (q > max)
                {
                    break;
                }
                kf++;
            }
        }

        public override string Problem
        {
            get
            {
                return @"In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p
How many different ways can £2 be made using any number of coins?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 73682;
            }
        }

    }
}
